\documentclass[12pt]{ctexart}
\usepackage{graphicx}
\usepackage{ctex}
\usepackage[a4paper,left=1.25in,right=1.25in,top=1in,bottom=1in]{geometry}

\title{作业一}
\author{刘小川  \\ 学号 3210105317}

\begin{document}
\maketitle

\subsection*{Question 1}

\textbf{Construct a Turning machine that reverses its input}

\subsection*{Solution 1}
算法思路：将要反转的字符串输入后，从字符的左端开始，让读写头一步步走到最右端，然后通过状态记录方式，将最右端字母改写成最左端的，然后返回到最左段，将最左端数字改为先前最右端的，然后这样一次循环，就将两端元素掉转，然后第二次循环便将左右两端第二位元素调换，一次类推，直到中央的元素，此时也完成了reverse操作。\par
下面是图灵机的具体定义：\par
外字母表 A=\{0,1\}\par
字母表 S=\{${\sqcup,0,1,*,0',1'}$\}\par
状态集合Q=$\{q_0,q_f,r_0,r_1,l_0,l_1,l_{0'},l_{1'}\}$\par
首先是对状态的解释，上面状态中*的状态作为一个还需转换的部分的最左端的标记，其余$l_0$和$l_1$分别代表向左前进的状态，0和1是最左端的数，因此到最右端的时候方便将最左端的数据传入。\par
有了以上字母表，外字母表q以及状态集合的定义，接下来可以定义转换函数。\par
$\delta$的定义从不同状态入手，那么先定义初始状态为$q_0$的转换函数。
由于外字母表只有\{0,1\},所以三种转换函数对应\par
$(q_0,0)\longmapsto(r_0,*,+1)$，
$(q_0,1)\longmapsto(r_1,*,+1)$，
$(q_0,\sqcup)\longmapsto(q_0,*,-1)$
\par 这样定义的含义便是若初始为$\sqcup$，则会向前遍历一步使图灵机工作立刻停止。若为0或1,则改为向右移动的状态，并且r后面的后缀记录最左边元素。并且将此位改为元素*，则方便返回时找到最左侧的元素。
接下来定义状态为$r_0,r_1$的转换函数。在中间过程为传递过程，所以不改变其中的元素，所以有\par
$(l_0,0)\longmapsto(l_0,0,-1)$，
$(l_0,1)\longmapsto(l_0,1,-1)$，\par
$(l_1,0)\longmapsto(l_1,0,-1)$，
$(l_1,1)\longmapsto(l_1,1,-1)$，\par
这种遍历知道碰见第一个在外字母表外的元素，那么该元素的左边第一个元素便是此次要交换地元素因此要把它改变，首先应完成向右前进变成向左前进\par
$(r_0,0')\longmapsto(l_{0'},0',-1)$，$(r_1,0')\longmapsto(l_{1'},0',-1)$\par
$(r_0,1')\longmapsto(l_{0'},1',-1)$，$(r_1,1')\longmapsto(l_{1'},1',-1)$\par
$(r_0,\sqcup)\longmapsto(l_{0'},\sqcup,-1)$,$(r_1,\sqcup)\longmapsto(l_{1'},\sqcup,-1)$

然后形成了向左前进，首先改写步骤的转换函数为\par
$(l_{0'},0)\longmapsto(l_0,0',-1)$,$(l_{0'},1)\longmapsto(l_1,0',-1)$\par
$(l_{1'},0)\longmapsto(l_0,1',-1)$,$(l_{1'},1)\longmapsto(l_1,1',-1)$\par
这样做的意义是将最右端的数字记录下来保存在l后缀中，同时修改了成为最左端的数字
然后就是不断返回到最左端：\par
$(l_0,0)\longmapsto(r_0,0,+1)$，
$(r_0,1)\longmapsto(r_0,1,+1)$，\par
$(r_1,0)\longmapsto(r_1,0,+1)$，
$(r_1,1)\longmapsto(r_1,1,+1)$，\par
直到遇到*，表示最左端已达到，则修改数字
$(l_0,*)\longmapsto(q_0,0,+1)$,$( _1,*)\longmapsto(q_0,1,+1)$\par
这样一次反转结束，完成了最左端与最右端元素互换，而且又回到了状态$q_0$，若转换没有结束则继续。最后我们按照奇偶性来做最后补充。\par
若字符串长度为奇数，则最后一个元素转换为 \par
$(l_0',*)\longmapsto(q_f,0,-1)$ ,$(l_1',*)\longmapsto(q_f,1,-1)$\par
若字符串为偶数，则最终的转换为
$(q_0,0')\longmapsto(q_f,0',-1)$,$(q_0,1')\longmapsto(q_f,1',-1)$
 由于没有对状态$q_f$进行转换函数定义，则图灵机工作停止，那么转换工作也完成。

\subsection*{Question 2}
\textbf{Construct a Turning machine that adds two numbers written in binary.}
\subsection*{Solution 2}
同课本上题目讲述相同，两个二进制数之间用加法相隔，该图灵机的设计如下：\par
外字母表$A=\{0,1,+\}$\par
字母表$S=\{0,1,+,\sqcup,0',1'\}$\par
状态集合$Q=\{q_0,f_1,s_1,j_0,j_1,r_0,r_1,k_0,k_1,h_0,h_1,q_f\}$\par
我们计算的思路是将第一个二进制数从最低位开始逐个加入到第二个数相应的位数，将结果覆盖至第二个二进制数中。在输入时，让第二个二进制数比第一个至少多一位，并且通过填充0使其最大位为0,因为我计划在第二个二进制数对应的位置储存结果，这样能保证结果长度不会超过原来二进制位置。如果长度不相同，可以用0来填充。接下来具体实现如下。\par
第一种转换是开始时\par
$(q_0,0)\longmapsto(f_1,0,+1)$, \par
$(q_01)\longmapsto(f_1,1,+1)$,\par
即读取第一个数的第一位时，开始寻找第一个数尚未未加的最后一位\par
$(f_1,0)\longmapsto(f_1,0,+1)$, \par
 $(f_1,1)\longmapsto(f_1,1,+1)$，\par
$(f_1,+)\longmapsto(s_1,+,-1)$,\par
$(f_1,0')\longmapsto(f_1,0',-1)$,\par
这里说明一下0‘意味着第一个二进制数中已经加完的数为0’，\par
$(s_1,0)\longmapsto(j_0,0',+1)$,\par
$(s_1,1)\longmapsto(j_1,0',+1)$,\par
这里$j_0$和$j_1$分别代表要在第二个二进制中对应位数加上0或1.\par
$(j_0,0')\longmapsto(j_0,0',+1)$,  \par
$(j_0,+)\longmapsto(r_0,+,+1),$\par
$(j_1,0')\longmapsto(j_1,0',+1)$,\par  $(j_1,+)\longmapsto(r_1,+,+1)$,\par
接下来寻找要第二个二进制数要加的对应的位数\par
$(r_0,0)\longmapsto(r_0,0,+1)$,\par$(r_0,1)\longmapsto(r_0,1,+1)$,\par
$(r_0,0')\longmapsto(k_0,0',-1),$\par$(r_0,1')\longmapsto(k_0,1',-1)$,\par
$(r_1,0)\longmapsto(r_1,0,+1)$,\par$(r_1,1)\longmapsto(r_1,1,+1)$,\par
$(r_1,0')\longmapsto(k_1,0',-1)$,\par$(r_1,1')\longmapsto(k_1,1',-1)$,\par
这样就进入两个一位二进制加法环节\par
$(k_0,0)\longmapsto(h_0,0',-1)$,\par$(k_0,1)\longmapsto(h_0,1',-1)$\par
$(k_1,0)\longmapsto(h_0,1',-1)$,\par$(k_1,1)\longmapsto(h_1,0',-1)$\par
在这个环节中比较重要的一部是怎么处理产生的进位，这里注意我要求第二位二进制最高位为0,且位数比第一个高，所以这样产生进位加法后不会超过原来位置\par
$(h_1,0)\longmapsto(h_0,1,-1)$,\par$(h_1,1)\longmapsto(h_1,0,-1)$,\par
$(h_0,0)\longmapsto(h_0,0,-1)$,\par$(h_0,1)\longmapsto(h_0,1,-1)$,\par
$(h_0,+)\longmapsto(h_0,+,-1)$,\par$(h_0,0')\longmapsto(h_0,0',-1)$,\par
$(h_0,\sqcup)\longmapsto(q_0,\sqcup,+1)$
如果加到了$q_0$所对应的数就是0‘，则加法完成则可以结束，加法后面的就是结果。\par
$(q_0,0')\longmapsto(q_f,0',+1)$
\par
由于没有定义$q_f$的转换函数，图灵机会停止。
\end{document}